//FA subsets
//$Id: subset.cpp 367 2010-03-13 15:50:03Z andrew.tsyganov $

#include "stdafx.h"

#include "fa.h"
#include "subset.h"
#include "utils.h"

using namespace std;

void States_Subset::insert(int const state_id)
{
    for (int i = 0; i < (int) states_id_.size(); ++i)
        if (states_id_[i] == state_id)
            return;

    states_id_.push_back(state_id);
}

bool States_Subset::contains(int const state_id) const
{
    for (int i = 0; i < (int) states_id_.size(); ++i)
        if (state_id == states_id_[i])
            return true;

    return false;
}

bool operator <=(States_Subset const& l, States_Subset const& r)
{
    if (l.size() > r.size())
        return false;

    for (int i = 0; i < (int) l.size(); ++i)
        if (!r.contains(l[i]))
            return false;

    return true; 
}

bool operator ==(States_Subset const& l, States_Subset const& r)
{
    if (l.size() != r.size())
        return false;

    for (int i = 0; i < (int) l.size(); ++i)
    {
        bool found = false;
        for (int j = 0; j < (int) r.size(); ++j)
            if (l[i] == r[j])
            {
                found = true;
                break;
            }

            if (!found)
                return false;
    }

    return true; 
}

bool operator !=(States_Subset const& l, States_Subset const& r)
{
    return !(l == r);
}

void States_Subset::intersect(States_Subset const& l, States_Subset const& r)
{
    states_id_.clear();

    int m = (int) l.size();
    int n = (int) r.size();

    if (m < n)
    {
        for (int i = 0; i < m; ++i)
        {
            bool found = false;
            for (int j = 0; j < n; ++j)
                if (l.states_id_[i] == r.states_id_[j])
                {
                    found = true;
                    break;
                }
                if (found)
                    states_id_.push_back(l.states_id_[i]);
        }
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            bool found = false;
            for (int j = 0; j < m; ++j)
                if (r.states_id_[i] == l.states_id_[j])
                {
                    found = true;
                    break;
                }
                if (found)
                    states_id_.push_back(r.states_id_[i]);
        }
    }
}

void States_Subset::join(States_Subset const& l, States_Subset const& r)
{
	states_id_.clear();

	int m = (int) l.size();
	int n = (int) r.size();

	if (m < n)
	{
        states_id_ = r.states_id_;

        for (int i = 0; i < m; ++i)
        {
            bool found = false;
            for (int j = 0; j < n; ++j)
                if (l.states_id_[i] == r.states_id_[j])
                {
                    found = true;
                    break;
                }
                if (!found)
                    states_id_.push_back(l.states_id_[i]);
        }
	}
	else
	{
        states_id_ = l.states_id_;

        for (int i = 0; i < n; ++i)
        {
            bool found = false;
            for (int j = 0; j < m; ++j)
                if (r.states_id_[i] == l.states_id_[j])
                {
                    found = true;
                    break;
                }
                if (!found)
                    states_id_.push_back(r.states_id_[i]);
        }
	}
}

string States_Subset::to_String() const
{
    string s;

    s = "{";
    for (int i = 0; i < (int) states_id_.size(); ++i)
        if (i < (int) states_id_.size() - 1)
            s += IntToString(states_id_[i]) + ",";
        else
            s += IntToString(states_id_[i]);
    s += "}";

    return s;
}

string States_Subset::to_String(FA const& a) const
{
    string s;

    s = "{";
    for (int i = 0; i < (int) states_id_.size(); ++i)
        if (i < (int) states_id_.size() - 1)
            s += a.states_[states_id_[i]] + ",";
        else
            s += a.states_[states_id_[i]];
    s += "}";

    return s;
}

States_Subset operator *(States_Subset const& l, States_Subset const& r)
{
    States_Subset res;

    int m = (int) l.size();
    int n = (int) r.size();

    if (m < n)
    {
        for (int i = 0; i < m; ++i)
        {
            bool found = false;
            for (int j = 0; j < n; ++j)
                if (l[i] == r[j])
                {
                    found = true;
                    break;
                }
                if (found)
                    res.insert(l[i]);
        }
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            bool found = false;
            for (int j = 0; j < m; ++j)
                if (r[i] == l[j])
                {
                    found = true;
                    break;
                }
                if (found)
                    res.insert(r[i]);
        }
    }

    return res;
}

States_Subset operator +(States_Subset const& l, States_Subset const& r)
{
    States_Subset res;

	int m = (int) l.size();
	int n = (int) r.size();

	if (m < n)
	{
        res = r;

        for (int i = 0; i < m; ++i)
        {
            bool found = false;
            for (int j = 0; j < n; ++j)
                if (l[i] == r[j])
                {
                    found = true;
                    break;
                }
                if (!found)
                    res.insert(l[i]);
        }
	}
	else
	{
        res = l;

        for (int i = 0; i < n; ++i)
        {
            bool found = false;
            for (int j = 0; j < m; ++j)
                if (r[i] == l[j])
                {
                    found = true;
                    break;
                }
                if (!found)
                    res.insert(r[i]);
        }
	}

    return res;
}

int FindInVector(std::vector<States_Subset> const& vs, States_Subset const& ss)
{
    for (int i = 0; i < (int) vs.size(); ++i)
        if (vs[i] == ss)
            return i;

    return -1;
}

//EOF!
